import java.util.*;

public class Partition {
    static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
}
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        if(pHead == null) return null;
        ListNode cur = pHead;
        ListNode prev = null;
        Stack<Integer> stack = new Stack<>();
        while(cur!=null){
            if(cur.val<x){
                stack.add(cur.val);
                if(cur==pHead){
                    pHead = pHead.next;
                    cur = pHead;
                }else{
                    prev.next = cur.next;
                    cur = prev.next;
                }
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        while(!stack.isEmpty()){
            ListNode node = new ListNode(stack.pop());
            node.next = pHead;
            pHead = node;
        }
        return pHead;
    }
}
